package leetcode.jianzhioffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-27 11:52
 **/
public class JianZhiOffer35 {
    //存储新链表节点和旧链表节点的映射
    Map<Node, Node> map = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        //如果节点在map中不存在，说明该节点还没有创建，进行递归回溯
        if (!map.containsKey(head)) {
            Node node = new Node(head.val);
            map.put(head, node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        //返回当前节点映射的新节点。
        return map.get(head);
    }

}

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
